//
// Created by hcDarren on 2018/8/25.
//

#ifndef NDK_DAY37_AS_LINKSTACK_H
#define NDK_DAY37_AS_LINKSTACK_H

#include <android/log.h>

#define TAG "MAIN_TAG"
#define LOGE(...) __android_log_print(ANDROID_LOG_ERROR,TAG,__VA_ARGS__)

// 定义的节点 Node。
template<class E>
class Node {
public:
    // 下一个节点
    Node<E> *next;
    E value; // 当前value
public:
    Node(E value, Node<E> *next) {
        this->value = value;
        this->next = next;
    }
    ~Node(){
        LOG("析构函数")
    }
};

// LinkStack
template<class E>
class LinkStack {
private:
    // 头节点
    Node<E> *head = NULL;
    // 弹栈，相当于size
    int index = -1;
    // 栈顶的节点，相当于last节点。
    Node<E> *top = NULL;
public:
    // 构造和析构
    LinkStack();
    ~LinkStack();

public:
    /**
     * 栈是否为空
     */
    bool isEmpty();

    /**
     * 弹出栈顶的元素
     */
    E pop();

    /**
     * 获取栈顶的元素但不弹出
     * @return
     */
    E peek();

    /**
     * 将元素压入栈中
     */
    void push(E e);

private:
    Node<E> *node(int index);
};

template<class E>
void LinkStack<E>::push(E e) {
    // 完善
    Node<E> *new_node = new Node<E>(e, NULL); // 新建一个节点
    if (top) { // top非空： 已经有元素了，新节点放在top的上面。
        top->next = new_node;
    } else {
        head = new_node; // 空的时候，新节点就是head。
    }
    top = new_node; // 新加进来的是top节点。
    index++;
}

// 弹 比较尴尬， 出栈。
template<class E>
E LinkStack<E>::pop() {
    assert(index >= 0); // 断言 index

    E value = top->value;
    delete top; // 删除top。
    // 讲 top 指向前一个元素  O(n) 复杂度 ，双向链表 O (1) 完善
    top = node(index - 1); // 将下一个元素，赋值给top。
    return value;
}

// 根据索引index，拿到元素E
template<class E>
Node<E> *LinkStack<E>::node(int index) {
    Node<E> *h = head;
    for (int i = 0; i < index; i++) {
        h = h->next;
    }
    return h;
}

template<class E>
LinkStack<E>::~LinkStack() { // 析构函数
    Node<E> *h = head;
    while (head) {
        Node<E> *next = h->next;
        delete h;
        head = next;
    }
    head = NULL;
}

template<class E>
LinkStack<E>::LinkStack() {

}

#endif //NDK_DAY37_AS_LINKSTACK_H
